/**
 * 647. 回文子串
 * https://leetcode-cn.com/problems/palindromic-substrings/
 */

// /**
//  * @param {string} s
//  * @return {number}
//  */
// function countSubstrings(s) {
//   const { length } = s;
//   const codes = new Array(length).fill(0);
//   for (let i = 0; i < length; i += 1) {
//     codes[i] = s.charCodeAt(i);
//   }
//   let count = 1;
//   let left = 0;
//   let right = 0;
//   for (let i = 1; i < length; i += 1) {
//     count += 1;
//     left = i - 1;
//     right = i + 1;
//     while (left >= 0 && right < length && codes[left] === codes[right]) {
//       count += 1;
//       left -= 1;
//       right += 1;
//     }
//     if (codes[i - 1] === codes[i]) {
//       count += 1;
//       left = i - 2;
//       right = i + 1;
//       while (left >= 0 && right < length && codes[left] === codes[right]) {
//         count += 1;
//         left -= 1;
//         right += 1;
//       }
//     }
//   }
//   return count;
// }

/**
 * 动态规划
 * @param {string} s
 * @return {number}
 */
function countSubstrings(s) {
  const { length } = s;
  const codes = new Array(length).fill(0);
  for (let i = 0; i < length; i += 1) {
    codes[i] = s.charCodeAt(i);
  }
  const dp = new Array(length);
  for (let i = 0; i < length; i += 1) {
    dp[i] = new Array(length).fill(false);
  }
  let count = 1;
  dp[length - 1][length - 1] = true;
  for (let i = length - 2; i >= 0; i -= 1) {
    dp[i][i] = true;
    count += 1;
    if (codes[i] === codes[i + 1]) {
      dp[i][i + 1] = true;
      count += 1;
    }
    for (let j = i + 2; j < length; j += 1) {
      if (codes[i] === codes[j]) {
        dp[i][j] = dp[i + 1][j - 1];
        if (dp[i][j]) {
          count += 1;
        }
      }
    }
  }
  return count;
}

console.log(countSubstrings('abc') === 3);
console.log(countSubstrings('aaa') === 6);
console.log(countSubstrings('a') === 1);
console.log(countSubstrings('aa') === 3);
